#include <pthread.h>
#include <semaphore.h>
#include <sys/mman.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include "prefetch_lib.h"
#include <sys/time.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <assert.h>
#include <deque>
#include <bitset>
#include <set>
#include <iostream>
#include <fstream>
#include <time.h>
#include <string.h>
#include <signal.h>
#include <syslog.h>
#include <sstream>
#include <sys/ioctl.h>

double progress;

volatile uint8_t spawned;
volatile int64_t counters[1000];
volatile int64_t counters2[1000];
volatile uint8_t unused[1000];

#define BUF_SIZE 1000

int count = 0;

pthread_t prefetch_thread, printer_thread;

int64_t last[1000];

#define PAGE_LOG_SIZE 12

std::bitset<1 << (32 - PAGE_LOG_SIZE)> prefetch_set;
//std::set<uint64_t> prefetch_set1;
std::deque<int*> prefetch_queue(4096);

#define PREFETCH_SIZE (32 * 1024 * 1024)

int prefetch_count;
int main_misses;
int x;

struct timeval prefetch_times[1000][4096];

static inline long tvdiff(struct timeval &end, struct timeval &start) {
  return  ((end.tv_sec - start.tv_sec) * 1000000) + (end.tv_usec - start.tv_usec);
}

static inline void tvadd(struct timeval &tv, long us) {
  tv.tv_usec += us;
  if (tv.tv_usec > 1000000) {
    ++tv.tv_sec;
    tv.tv_usec -= 1000000;
  }
}

volatile static int advise_counter[1 << 20];

struct elem {
  int *addr;
  elem *next;
  
  elem(int *a) : addr(a) { }
};

const int ADVICE_SIZE = 4096 * 1;

struct bqueue {
  static const int COUNT = 10000;
  static const int DELTA_T = 1000;
  elem* heads[COUNT];
  
  inline int cur() {
    struct timeval cur;
    gettimeofday(&cur, 0);
    static const int subindex = 1000000 / DELTA_T;
    int s = cur.tv_sec % (COUNT / subindex);
    int us = cur.tv_usec % subindex;
    return s * subindex + us;
  }  
  
  // specifies that "addr" should be prefetched at "tv"
  inline void push(struct timeval *tv, int *addr) {  
    if (tv == 0) { // just prefetch
      madvise((void*)((unsigned int)addr & ~4095), ADVICE_SIZE, MADV_WILLNEED);      
//      __sync_add_and_fetch(advise_counter + ((unsigned int)addr >> 12), 1);    
      return;
    }
  
    struct timeval cur;
    gettimeofday(&cur, 0);
    
    long diff = tvdiff(*tv, cur);

    if (diff < 2 * DELTA_T) { // too close to current bin 
      madvise((void*)((unsigned int)addr & ~4095), ADVICE_SIZE, MADV_WILLNEED);;
      return;
    }
    
    for (; diff >= DELTA_T * COUNT; diff = tvdiff(*tv, cur))
      usleep(20);
    
    diff /= DELTA_T;
    
    elem *e = new elem(addr);
    e->next = __sync_lock_test_and_set(heads + diff, e);
  }

  void advise() {
    int index = cur();
    elem *e = __sync_lock_test_and_set(heads + index, 0);
    for (; e != 0;) {
//      printf("advising %u\n", ((unsigned int)(e->addr) & ~4095));
      madvise((void*)((unsigned int)(e->addr) & ~4095), ADVICE_SIZE, MADV_WILLNEED);
      elem *n = e->next;
      delete e;
      e = n;
    }
  }  
};

static bqueue *Q = new bqueue();

volatile int phase = 0;

int iscached(int *addr) {
  unsigned char c;  
  mincore((void*)((unsigned int)addr & ~4095), 4096, &c);
  return c & 1;
}

static volatile  long fetch_counter[1000];

const long DELAY_COUNTER_SAMPLE = 8192 * 64;

unsigned int last_fetch[1000];

void check(int *addr, int id) {
  if (phase > 0 && counters[id] < 5)
    return;
    
  ++fetch_counter[id];
      
//  __sync_fetch_and_add(counters2 + id, 1); 

/*  
  unsigned int sa = (unsigned int)addr >> 12;
  if (sa == last_fetch[id])
    return;
  last_fetch[id] = sa;
*/
/*
  
  if (__sync_sub_and_fetch(advise_counter + ((unsigned int)addr >> 12), 1) == 0) {  
//    madvise((void*)((unsigned int)addr & ~4095), 4096, MADV_DONTNEED);
//    printf("evicting pages %u\n", ((unsigned int)addr >> 12));
  }

*/


  long fci = ++fetch_counter[id];
  if (fci % DELAY_COUNTER_SAMPLE == 0) {
    fci /= DELAY_COUNTER_SAMPLE;
    struct timeval cur;
    gettimeofday(&cur, 0);
    long delay = tvdiff(cur, prefetch_times[id][fci]);
//    printf("delay[%ld] = %ld\n", fci, delay / 1000);
  }
  
  if (phase == 0 && !iscached(addr)) {
    ++counters[id];
    syslog(LOG_ERR, "                  C %x\n", (unsigned int)addr >> 12);
  }
}

void* fetch_entry(void *data) {
  for (;;) {  
    Q->advise();
    usleep(500);
  }
}

static volatile long prefetch_counter[1000];

static unsigned int last_prefetch[1000];

void prefetch(int *addr, int id) {


//  if (phase == 0) // check and set
  phase = 1;

  ++prefetch_counter[id];
  
//  int64_t c = __sync_sub_and_fetch(counters2 + id, 1);

/*
  unsigned int sa = (unsigned int)addr >> 12;
  if (sa == last_prefetch[id])
    return;
  last_prefetch[id] = sa;
*/
  // don't prefetch if behind the main computation
  if (fetch_counter[id] > prefetch_counter[id] - 250)
    return;

  
//  const int64_t MAX_GAP = (int64_t)2048 * (int64_t)32768; // multiplication
  const int64_t MAX_GAP = (int64_t)1 * (int64_t)2048; // 2layers
//  const int64_t MAX_GAP = (int64_t)32768 * (int64_t)32768; // buk
  
  // synchronize with main computation
  while (prefetch_counter[id] > fetch_counter[id] + MAX_GAP) {
//    puts("waiting\n");
    usleep(500);
  }



//  if (!iscached(addr)) {
//    syslog(LOG_ERR, "                  P %x\n", (unsigned int)addr >> 12);
//  }

/*
  struct timeval tv;
  gettimeofday(&tv, 0);
*/

/*  
  long pci = prefetch_counter[id];
  if (pci % DELAY_COUNTER_SAMPLE == 0) {
    pci /= DELAY_COUNTER_SAMPLE;
    gettimeofday(&prefetch_times[id][pci], 0);
  }
*/

  Q->push(0, addr);
  
//  madvise((void*)((unsigned int)addr & ~4095), 4096, MADV_WILLNEED);
  return; 
}

void init() {
}

void fetch(int *addr, int id) {
}

void fetch_init() {
//  pthread_create(&prefetch_thread, 0, fetch_entry, 0);
/*

  pthread_create(&printer_thread, 0, printer, 0);
  prefetch_stream.open("prefetch_log", std::ios_base::trunc | std::ios_base::out);
  fetch_stream.open("fetch_log", std::ios_base::trunc | std::ios_base::out);
*/
}

void turn_logging(char on) {
  char cmd[64];

  sprintf(cmd, "echo %d > /proc/%d/cache_acct", on, getpid());
  system(cmd);
}

